package org.example.algorithm.graph;

import java.util.*;

public class TimetableSolution {
    private boolean valid = true;

    public static void main(String[] args) {
        int[][] prerequisites = {{1, 0}};
        int numCourses = 2;
        TimetableSolution solution = new TimetableSolution();
        int[] res = solution.findOrder(numCourses, prerequisites);
        for (int item: res) {
            System.out.println(item);
        }
    }

    //DFS
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res= new int[numCourses];
        if (prerequisites.length == 0) {
            for (int i=0;i<numCourses;i++) {
                res[i] = i;
            }
            return res;
        }
        List<Integer>[] coursePre = new ArrayList[numCourses];
        Arrays.setAll(coursePre, e->new ArrayList<>());
        for (int i=0;i<prerequisites.length;i++) {
            coursePre[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        int[] visit = new int[numCourses];
        Stack<Integer> orderStack = new Stack<>();
        for (int i=0;i<numCourses && valid;i++) {
            if (visit[i] == 0) {
                dfs(coursePre, i, visit, orderStack);
            }
        }
        if (!valid) {
            return new int[0];
        }
        int index = 0;
        while (!orderStack.isEmpty()) {
            res[index++] = orderStack.pop();
        }
        return res;
    }

    private void dfs(List<Integer>[] prerequisites, int i, int[] visit, Stack<Integer> orderStack) {
        visit[i] = 1;
        for (int item: prerequisites[i]) {
            if (visit[item] == 1) {
                valid = false;
                return;
            } else if(visit[item] == 0) {
                dfs(prerequisites, item, visit, orderStack);
            }
        }
        visit[i] = 2;
        orderStack.push(i);
    }

    //BFS
    public int[] findOrder2(int numCourses, int[][] prerequisites) {
        if (prerequisites.length == 0) {
            int[] res= new int[numCourses];
            for (int i=0;i<numCourses;i++) {
                res[i] = i;
            }
            return res;
        }
        List<Integer>[] coursePre = new ArrayList[numCourses];
        Arrays.setAll(coursePre, e->new ArrayList<>());
        int[] coursePreCount = new int[numCourses];
        for (int i=0;i<prerequisites.length;i++) {
            coursePre[prerequisites[i][1]].add(prerequisites[i][0]);
            coursePreCount[prerequisites[i][0]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i=0;i<numCourses;i++) {
            if (coursePreCount[i] == 0) {
                queue.offer(i);
            }
        }
        int[] res = new int[numCourses];
        int cur = 0;
        int courseCount = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            courseCount++;
            res[cur++] = course;
            for (int item: coursePre[course]) {
                coursePreCount[item]--;
                if (coursePreCount[item] == 0) {
                    queue.offer(item);
                }
            }
        }
        if (courseCount != numCourses) {
            return new int[0];
        }
        return res;
    }
}
